package com.howtoplayalgorithm.divideandconquer;

import java.math.BigDecimal;
import java.math.BigInteger;

public class Karatsuba {
    /**
     * 使karatsuba算法触发的被乘数与乘数的位数
     */
    public static final int KARATSUBA_THRESHOLD = 100;

    /**
     * karatsuba乘法算法,目前这个写法要求a，b约定分割的位数相同
     * a * b = (ahigh * 2^alowbit + alow)(bhigh*2^blowbit + blow) = (ahigh*bhigh * 2^(alowbit+blowbit)) + (ahigh*blow * 2^alowbit + alow*bhigh*2^blowbit) + alow*blow
     * 如果上述式子中，alowbit==blowbit,则可以化为
     * ahigh*bhigh * 2^(2*alowbit)) + (ahigh*blow + alow*bhigh）*2^alowbit + alow*blow
     * = ahigh*bhigh * 2^(2*alowbit)) + ((ahigh+alow)*(bhigh+blow)-ahigh*bhigh - alow*blow)*2^alowbit + alow*blow
     *
     * 看multiply的源码即可
     * @param a
     * @param b
     * @return
     */
    public static BigInteger multi(BigInteger a, BigInteger b){
        int abit,bbit = b.bitLength();
        if((abit = a.bitLength()) <= KARATSUBA_THRESHOLD && (bbit) <= KARATSUBA_THRESHOLD){
            return a.multiply(b);
        }
        //将a，b分解为多个小乘数的组合
        int aShift = abit/2;
        BigInteger aHigh = a.shiftRight(aShift);
        BigInteger aLow = a.subtract(aHigh.shiftLeft(aShift));

        BigInteger bHigh = b.shiftRight(aShift);
        BigInteger bLow = b.subtract(bHigh.shiftLeft(aShift));

        BigInteger aHighbHigh = aHigh.multiply(bHigh);
        BigInteger aLowbLow = aLow.multiply(bLow);
        BigInteger messy = aHigh.add(aLow).multiply(bHigh.add(bLow));

        return aHighbHigh.shiftLeft(2*aShift).add(messy.shiftLeft(aShift)).add(aLowbLow);
    }


    public static void main(String[] args){

        BigInteger a = new BigInteger("33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333" +
                "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333" +
                "33333333333333333333333333333333333333333333333333333333333333333333333333" +
                "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333");

        BigInteger b = new BigInteger("33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333" +
                "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333" +
                "33333333333333333333333333333333333333333333333333333333333333333333333333" +
                "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333");

        System.out.println(a.multiply(b));
        System.out.println(multi(a,b));
    }
}
